package LineCode.剑指Offer.查找;

/**
 * 二维数组中的查找
 *
 * 题目描述
 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 */
public class 二维数组 {

    //test
    public static void main(String[] args) {
        int[][] nums = new int[][]{{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7}};
        int x = 4;
        System.out.println(Find(x, nums));
        System.out.println(Find2(x, nums));
    }

    /**
     * 一开始的思路：一般二维遍历 + 遇到大于 x 的数字便过
     * @param target
     * @param array
     * @return
     */
    public static boolean Find(int target, int [][] array) {
        try {
            for (int i = 0; i < array.length && target >= array[i][0]; i++) {
                for (int j = 0; j < array[i].length && target >= array[i][j]; j++) {
                    if (array[i][j] == target)
                        return true;
                }
            }
            return false;
        } catch (Exception e) {
            return false;
        }
    }


    /**
     * 左下角开始
     * @param target
     * @param array
     * @return
     */
    public static boolean Find2(int target, int [][] array) {
        try {
            int row = array.length;
            int col = array[0].length;
            int j = 0;
            for (int i = row-1; i >= 0 && j < col;) {
                if (array[i][j] == target)
                    return true;
                if (target > array[i][j])
                    j++;
                if (target < array[i][j])
                    i--;
            }
            return false;
        } catch (Exception e) {
            return false;
        }
    }

}
